package lanqiao._02算法训练.page01;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 问题描述
 * 　　将一个数N分为多个正整数之和，即N=a1+a2+a3+…+ak，定义M=a1*a2*a3*…*ak为N的潜能。
 * 　　给定N，求它的潜能M。
 * 　　由于M可能过大，只需求M对5218取模的余数。
 * 输入格式
 * 　　输入共一行，为一个正整数N。
 * 输出格式
 * 　　输出共一行，为N的潜能M对5218取模的余数。
 * 样例输入
 * 10
 * 样例输出
 * 36
 * 数据规模和约定
 * 　　1<=N<10^18
 * 思路：
 * 潜能应该是最大的乘积
 * 2 = 1 * 1  最大2
 * 3 = 1 * 2  最大3
 * 4 = 1 * 3 = 2 * 2 最大4
 * 5 = 1 * 4 = 2 * 3 最大6
 * 6 = 1 * 5 = 2 * 4 = 3 * 3 最大9
 * 分成 2 和 3 保证乘积最大
 * 尽可能分成更多的3
 * @since 2022 - 10 - 29 - 23:35
 */
public class _08数的潜能 {
}
class Main8{
    static int MOD = 5218;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        if(n <= 3) {
            System.out.println(n);
            return;
        }
        //计算可分成3的个数，不足用2补
        if(n % 3 == 0){
            System.out.println(pow(3, n / 3));
        }else if(n % 3 == 1){
            System.out.println(4 * pow(3, (n - 4) / 3) % MOD);
        }else{
            System.out.println(2 * pow(3, n / 3) % MOD);
        }
    }
    //快速幂运算 递归形式
    public static int pow(int a, long exp){
        if(exp == 0) return 1;
        if(exp == 1) return a % MOD;
        int res = pow(a, exp / 2);
        if(exp % 2 == 0){
            return res * res % MOD;
        }else{
            return a * res * res % MOD;
        }
    }
    //迭代形式
    private static long pow1(int a, long n) {
        if (n == 0) return 1;
        long res = a;
        long ex = 1;
        while ((ex << 1) <= n) {      //尝试翻倍
            res  = res * res % MOD;           //翻倍--a^2--a^4---x---a^n 加倍后，逼近或等于a^n
            ex <<= 1;             //已经翻倍
        }
        //差n-ex次方没有乘到结果里
        return res * pow1(a, n - ex) % MOD;
    }
}
class Main8_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // n 的取值超过了int最大值
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], (dp[i - j] * j) % 5218);
            }
        }
        System.out.println(dp[n]);
    }
}